• Home
  • About
  • Posts
  • 1. 개요

  • 2. 동작

    • 2.1. 데이터 삽입
    • 2.2. 데이터 삭제
  • 3. 시간 복잡도

    • 3.1. 데이터 삽입
    • 3.2. 데이터 삭제
  • 4. 구현

  • 5. 활용

힙(Heap) 자료구조

📅 2023-03-05
🖋️ Byongho96

1. 개요

여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리.

2. 동작

아래 동작 설명은 최대힙을 기준으로 설명한다.

2.1. 데이터 삽입

  1. 힙의 가장 끝의 자리에 노드를 삽입한다.
  2. 해당 노드와 부모 노드를 서로 비교한다.
  3. 해당 노드가 부모 노드보다 클 경우, 두 노드의 위치를 바꾼다.
  4. 해당 노드가 부모 노드보다 작아지거나, 루트 노드가 될 때까지 2~3의 과정을 반복한다.

2.2. 데이터 삭제

  1. 루트 노드를 제거한다.
  2. 루트 자리에 가장 마지막 노드를 삽입한다.
  3. 해당 노드와 자식 노드(들)을 비교한다.
  4. 해당 노드가 자식 노드(들)보다 작을 경우, 두 노드의 위치를 바꾼다.
  5. 해당 노드가 자식 노드(들)보다 커지거나, 리프 노드가 될 때까지 3~4의 과정을 반복한다.

3. 시간 복잡도

데이터의 크기 N

3.1. 데이터 삽입

O(logN) 트리의 깊이가 logN이기 때문에 최대 logN 번의 비교와 치환 연산이 일어난다.

3.2. 데이터 삭제

O(logN) 트리의 깊이가 logN이기 때문에 최대 logN 번의 비교와 치환 연산이 일어난다.

4. 구현

  • Python 코드

    # 참고한 블로그 글: https://daimhada.tistory.com/108
    
    class MaxHeap:
    
        # 생성자 함수
        def __init__(self):
            self.queue = []
    
        # 삽입 함수
        def insert(self, n):
            self.queue.append(n)        # 힙의 마지막에 노드 추가
            current_index = len(self.queue) - 1
            while 0 < current_index:    # 루트 노드가 될때까지 반복
                parent_index = self.parent(current_index)
                if self.queue[parent_index] < self.queue[current_index]:    # 부모 노드보다 클 경우
                    self.swap(parent_index, current_index)                  # 치환
                    current_index = parent_index
                else:                   # 그렇지 않을 경우, 비교 연산 중지
                    break
    
        # 삭제 함수
        def delete(self):
            last_index = len(self.queue) - 1
            if last_index < 0:
                return -1
            self.swap(0, last_index)    # 루트 노드와 마지막 노드 치환
            max_value = self.queue.pop()
            self.maxHeapify(0)          # 루트 노드로부터 masHeapify 동작
            return max_value
    
    
        # heapify 정렬 함수
        def maxHeapify(self, i):
            left_index  = self.left_child(i)
            right_index = self.right_child(i)
            last_index = len(self.queue) - 1
    
            max_index = i
            if left_index <= last_index and self.queue[max_index] < self.queue[left_index]:
                max_index = left_index
            if right_index <= last_index and self.queue[max_index] < self.queue[right_index]:
                max_index = right_index
    
            if max_index != i:  # 현재 노드가 자식 노드(들)보다 작을 경우, 현재 노드를 자식 노드와 치환
                self.swap(i, max_index)
                self.maxHeapify(max_index)
    
        # 보조 함수
        def swap(self, i, j):
            self.queue[i], self.queue[j] = self.queue[j], self.queue[i]
    
        def parent(self, i):
            return (i - 1) // 2
    
        def left_child(self, i):
            return 2 * i + 1
    
        def right_child(self, i):
            return 2 * i + 2
    
        # special methods
        def __str__(self):              # 출력
            return str(self.queue)
    
        def __getitem__(self, index):   # 인덱싱
            return self.queue[index]
    
        def __iter__(self):             # iterable
            self.index = 0
            return self
    
        def __next__(self):             # iterable
            if len(self.queue) <= self.index:
                raise StopIteration
    
            self.index += 1
            return self.queue[self.index - 1]
    
        def __contains__(self, item):   # in 메소드
            return item in self.queue
    
        def __bool__(self):             # Boolean 판단
            return bool(self.queue)
    

5. 활용

  • Dijkstra (Greedy Algorithm)
이전 포스트

트리(Tree) 자료구조

작성자 프로필
전체 글 (127)
  • Animation
    • Backend
      • Django
      • Spring
    • DevOps
      • AWS
      • CI&CD
      • Docker
      • Git
      • Gunicorn
      • Kubernetes
      • Nginx
    • Frontend
      • Gatsby
      • React
      • Vue
    • Knowledge
      • .etc
      • Algorithm
      • Data Structure
      • Database
      • Design Pattern
      • Interview
      • Network
      • Web
    • Language
      • CSS
      • HTML
      • Java
      • JavaScript
      • Linux
      • Python

    Copyright © 2023 Byongho96  & Powered by Gatsby